//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。
//
//
//
// 参考以下这颗二叉搜索树：
//
//      5
//    / \
//   2   6
//  / \
// 1   3
//
// 示例 1：
//
// 输入: [1,6,3,2,5]
//输出: false
//
// 示例 2：
//
// 输入: [1,3,2,6,5]
//输出: true
//
//
//
// 提示：
//
//
// 数组长度 <= 1000
//
//
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 726 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function verifyPostorder(postorder: number[]): boolean {
    //? 数组长度小于2必然是
    if (postorder.length <= 2) {
        return true
    }
    //? 后序遍历的根在最后
    const root = postorder.pop()
    //? 找到第一个大于根节点的节点(findIndex返回满足条件的第一个索引)
    let index = postorder.findIndex(num => num > root)
    //? 如果没有找得到 index就是最末尾 也就是只有左子树
    index = index === -1 ? postorder.length : index
    //? 分左右树
    const left = postorder.slice(0, index)
    const right = postorder.slice(index)
    //? 递归 every方法用于检查数组中的所有元素是否都满足指定的条件 如是空数组调用every 则必为true
    //? 递归条件已经被我们找到：左子树的所有值要小于根节点的值&&右子树的所有值要大于根节点的值&&左子树是某二叉搜索树的后序遍历&&右子树是某二叉搜索树的后序遍历
    return left.every(num => num < root) && right.every(num => num > root) && verifyPostorder(left) && verifyPostorder(right)

};
//leetcode submit region end(Prohibit modification and deletion)
